﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0187_FindSmallestSetOfVertices : IAlgorithm
    {
        // 1557. 可以到达所有点的最少点数目

        // 给你一个 有向无环图 ， n 个节点编号为 0 到 n-1 ，以及一个边数组 edges ，其中 edges[i] = [fromi, toi] 表示一条从点  fromi 到点 toi 的有向边。
        // 找到最小的点集使得从这些点出发能到达图中所有点。题目保证解存在且唯一。
        // 你可以以任意顺序返回这些节点编号。

        // 提示：
        //  2 <= n <= 10^5
        //  1 <= edges.length <= min(10^5, n* (n - 1) / 2)
        //  edges[i].length == 2
        //  0 <= fromi, toi<n
        //  所有点对 (fromi, toi) 互不相同。

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public IList<int> FindSmallestSetOfVertices(int n, IList<IList<int>> edges)
        {
            int[] inDegrees = new int[n];
            foreach (var item in edges)
                inDegrees[item[1]]++;
            var res = new List<int>();
            for (int i = 0; i < n; i++)
                if (inDegrees[i] == 0) res.Add(i);
            return res;
        }
    }
}
